Requests to shared resources in an electronic processing device must be controlled in order to provide a guarantee for the service for the individual service users in a category that as a whole has guaranteed latency rate service, which is defined below, and a high efficiency of the shared resource. An example of a shared resource in an electronic processing device is a memory. Electronic processing devices may comprise one or more processors. Said processors need to be connected to a memory in order to be able to execute a program. Many different types of memories exist. One type of memory that is commonly used is Dynamic Random Access Memory (DRAM). In a DRAM, only a limited number of memory rows per memory bank, typically only one memory row per memory bank, are accessible at a given time either for reading or writing. In order to change between rows which are accessible commands have to be sent to the DRAM. In order to switch between reading from the memory and writing to the memory, the memory controller must wait several clock cycles. A processor that is adapted to be connected to a DRAM usually has a DRAM controller arranged on the same chip as the processor. The DRAM controller is arranged to control one or more DRAM(s) connected to the DRAM controller by a DRAM interface. For the above mentioned reasons, queues of requests for memory access to the DRAM has to be re-ordered in order to be able to provide high efficiency. Some users of the shared resources benefit from a latency rate service. Latency rate service means that after time τ seconds in a busy period, at least max(0, (τ−θ)×p) requests have been served, i.e., the maximum of 0 and ((τ−θ)×φ. θ is initial latency, i.e., the maximum delay in seconds between when the first request in a busy period is sent and when the request is served. ρ is the rate, i.e. the minimum number of requests that are served per second. In case the processing device is set up to serve one request per clock cycle the rate is equal to the clock frequency of the processing device.
It is possible to use a simple up-down counter to guarantee the shared service for all such users, but the share to each individual user is not known and the initial latency for each individual user may be unlimited. For the case of DRAM controllers, the users are traffic flows and the traffic flows that should get similar service belong to the same traffic category. Bus arbitration techniques to reduce access latency are known from the prior art. The memory requests are scheduled based at least in part on desired latency.
It is known from the prior art to control the processing of requests of a first category having a first priority as well as controlling the processing of requests of a second category having a second priority. The priorities may change over time.
When there is no limitation for the re-ordering in the queue, the guarantee on the shared resource cannot be used to derive a guarantee for the service for the individual service users. A request from any user could then be overtaken by an unlimited number of later arriving requests which would lead to starvation, i.e., to a request never receiving any service. Overtaking means that a later request is served before an earlier request. The trivial solution to use an in-order First-In-First-Out (FIFO) queue has the flaw that it does not allow high efficiency of the shared resource, at least in the case of an interface to a DRAM of the type Double Data Rate (DDR), which is a well known standard. This is especially true for higher frequency DRAM:s of the types called DDR3 and DDR4, which are later standards of DDR.
Previous attempts to provide starvation-free service include an ageing mechanism and a timeout mechanism for memory request reordering. The ageing mechanism increases the priority of requests as the requests get older. When a request has reached the highest priority the timeout mechanism masks all other requests to make sure that the highest priority request will be served.
Another previous attempt uses FIFO service order to provide latency-rate guarantee per traffic flow. Only Read (RD) and Write (WR) commands are here kept in order. Precharge (PRE) and Activate (ACT) commands may be issued in advance using a technique called look ahead.
All previous attempts suffer from insufficient efficiency of the DRAM for high demand users.